package com.wrial.sort;
/*
 * @Author  Wrial
 * @Date Created in 9:37 2020/8/26
 * @Description
 */

public class HeapSort {

    public static void heapSort(int[] arr) {

        for (int i = 0; i < arr.length / 2; i++) {
            heapHelper(arr, arr.length, i);
        }
        for (int i = arr.length - 1; i >= 0; i--) {
            swap(arr, 0, i);
            heapHelper(arr,i,0);
        }
        for (int i : arr) {
            System.out.println(i);
        }

    }

    private static void heapHelper(int[] arr, int length, int i) {
        int index = i * 2 + 1;
        int k = i;
        int temp = arr[i];
        while (index < length) {

            if (index + 1 < length) {
                index = arr[index] > arr[index + 1] ? index : index + 1;
            }
            //如果不是最大就将下面的替换上来，当前k保留继续向下搜索
            if (temp < arr[index]) {
                arr[k] = arr[index];
                k = index;
                index = 2 * k + 1;
            } else break;

        }
        arr[k] = temp;
    }
    private static void swap(int[] arr, int l, int r) {
        int temp = arr[l];
        arr[l] = arr[r];
        arr[r] = temp;
    }

    public static void main(String[] args) {
        int[] arr = new int[]{87,-5,8,1,9};
        heapSort(arr);
    }

}
